class Solution {
public:
    void sortColors(vector<int>& nums) {
        //三路划分法解决这个题目
        //三路划分也就是选定一个基准值，将小于这个基准值的放在后面中间放基准值，然后就是大于基准值的放在最前面
        int paix = 1;
        int left = -1;
        int cur = 0;
        //left左边的元素就是小于基准值的元素，left右边的元素就是等于基准值的元素，cur左边的元素就是等于基准值的元素，
        //cur右边的元素就是未知的元素
        int n = nums.size();
        int end = n-1;//end右边就是大于基准值的元素
        while(cur<=end)
        {
            if(nums[cur]<paix)
            {
                //小于基准值
                swap(nums[++left],nums[cur]);
                cur++;
            }
            else if(nums[cur] == paix)
            {
                //等于基准值
                cur++;
            }
            else
            {
                //大于基准值
                swap(nums[cur],nums[end]);
                end--;
                //这里cur不需要让cur进行移动，因为交换过去的这个元素并不知道值得大小
            }
        }
    }
};